/*
 * @lc app=leetcode.cn id=911 lang=typescript
 *
 * [911] 在线选举
 */

// @lc code=start
class TopVotedCandidate {
  tops: number[];
  times: number[];
  constructor(persons: number[], times: number[]) {
    this.times = times;
    // 预处理每个时间点的最高得票数的人，方便q函数查询
    this.tops = [];
    let voteCount = new Map<number, number>();
    let maxVote = -1;
    voteCount.set(-1, -1);

    for (let person of persons) {
      voteCount.set(person, (voteCount.get(person) || 0) + 1);
      if (voteCount.get(person) >= voteCount.get(maxVote)) {
        maxVote = person;
      }
      this.tops.push(maxVote);
    }
  }

  q(t: number): number {
    let l = 0;
    let r = this.times.length - 1;
    // 二分查找最后一个小于等于t的时间点
    while (l < r) {
      let mid = l + ((r - l + 1) >> 1);
      if (this.times[mid] <= t) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    return this.tops[l];
  }
}

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * var obj = new TopVotedCandidate(persons, times)
 * var param_1 = obj.q(t)
 */
// @lc code=end
